package com.gule.gl.leetcode.editor.javabook;

/**
 * @Auther: gl
 * @Date: 2020/2/12 13:23
 * @Description: 判断一个数组是否是某个树的后续遍历所遍历出来的
 * todo 比较好的题目
 */
@Deprecated
public class JudgeArrayIsHouxubianli {

    private boolean judgeArrayIsHouxubianli(int[] arr, int start, int end) {
        int root = arr[arr.length - 1];

        int i, j;
        for (i = start; i < end; i++) {
            //说明从大于这个数开始的都是根节点的又节点，小于的都是左节点的
            if (arr[i] > root) {
                break;
            }
        }
        //如果是后续遍历，大于这个数开始的都是根节点的又节点，否则就不满足后序遍历
        for (j = i; j < end; j++) {
            if (arr[j] < root) {
                return false;
            }
        }
        boolean iIs = true;
        boolean jIs = true;
        if (i > start) {
            iIs = judgeArrayIsHouxubianli(arr, start, i - 1);
        }
        if (j < end) {
            jIs = judgeArrayIsHouxubianli(arr, j, end - 1);
        }
        return iIs && jIs;
    }
}
